package _binary_tree;

import common.TreeNode;
import org.junit.Assert;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;

/*

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html
https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
144. 二叉树的前序遍历

示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]

示例 3：
输入：root = []
输出：[]

示例 4：
输入：root = [1]
输出：[1]
 */
public class leetcode_144_Java {
    @Test
    public void test_1() {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        List<Integer> actual = preorderTraversal(root);
        List<Integer> expect = new ArrayList<>(List.of(1, 2, 3));
        Assert.assertEquals(expect.toString(), actual.toString());
    }

    @Test
    public void test_2() {
        TreeNode root = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        TreeNode n8 = new TreeNode(8);
        TreeNode n9 = new TreeNode(9);
        root.left = n2;
        root.right = n3;
        n2.left = n4;
        n2.right = n5;
        n5.left = n6;
        n5.right = n7;
        n3.right = n8;
        n8.left = n9;

        List<Integer> actual = preorderTraversal(root);
        List<Integer> expect = new ArrayList<>(List.of(1, 2, 4, 5, 6, 7, 3, 8, 9));
        Assert.assertEquals(expect.toString(), actual.toString());
    }

    @Test
    public void test_3() {
        TreeNode root = null;
        List<Integer> actual = preorderTraversal(root);
        List<Integer> expect = new ArrayList<>();
        Assert.assertEquals(expect.toString(), actual.toString());
    }

    @Test
    public void test_4() {
        TreeNode root = new TreeNode(1);
        List<Integer> actual = preorderTraversal(root);
        List<Integer> expect = new ArrayList<>(List.of(1));
        Assert.assertEquals(expect.toString(), actual.toString());
    }

    private List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        traverse(root, list);
        return list;
    }

    private void traverse(TreeNode node, List<Integer> list) {
        if (null == node) {
            return;
        }
        list.add(node.val);
        traverse(node.left, list);
        traverse(node.right, list);
    }
}
